// step 1# 自定义比较函数：排序规则
int cmp(const void *p1, const void *p2) {
    int *pp1 = *(int**)p1;
    int *pp2 = *(int**)p2;
    // step 1.1# 身高相同，按k值从小到大排序
    // step 1.2# 身高不同，按身高从大到小排序
    return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp2[0] - pp1[0];
}

// step 2# 辅助函数：将[start, end)区间的元素整体后移一位
void moveBack(int **people, int peopleSize, int start, int end) {
    int i;
    for(i = end; i > start; i--) {
        people[i] = people[i-1];
    }
}

// step 3# 主函数：重建队列
int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
    int i;
    
    // step 3.1# 按规则排序
    qsort(people, peopleSize, sizeof(int*), cmp);

    // step 3.2# 按k值插入到正确位置
    for(i = 0; i < peopleSize; ++i) {
        int position = people[i][1];    // step 3.2.1# 获取插入位置
        int *temp = people[i];           // step 3.2.2# 暂存当前元素
        moveBack(people, peopleSize, position, i); // step 3.2.3# 将区间元素后移一位
        people[position] = temp;         // step 3.2.4# 将元素插入指定位置
    }
    
    // step 3.3# 设置返回参数
    *returnSize = peopleSize;
    *returnColumnSizes = (int*)malloc(sizeof(int) * peopleSize);
    for(i = 0; i < peopleSize; ++i) {
        (*returnColumnSizes)[i] = 2;    // 每个人属性是2列（身高+人数）
    }
    
    // step 3.4# 返回结果
    return people;
}
